1. Field of the Invention
The present invention pertains generally to the field of computational complexity and, more particularly, to the solving of problems in the complexity class NP. The field of computational complexity is tied to the use of computers and machines.
2. Description of Related Art
Computational complexity theory is a branch of computer science that focuses on classifying computational problems according to their inherent difficulty. Computational complexity theory determines the practical limits on what computers can and cannot do.
In the context of computational complexity issues, a computational problem is understood to be a task that is in principle amenable to being solved by a computer. For example, primality testing is the problem of determining whether a given number is prime or not. The instances of this problem are natural numbers, and the solution to an instance is yes or no based on whether the number is prime or not.
A problem is regarded as inherently difficult if solving the problem requires a large amount of resources, irrespective of the algorithm used for solving it. The computational complexity theory formalizes this intuition, by introducing mathematical models of computation to study the problems and quantifying the amount of resources, such as computational time and computer storage, needed to solve them. Other complexity measures are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing).
Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A distinction between computational complexity theory and analysis of algorithms is that the analysis of algorithms is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas computational complexity asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available computer-related resources is what distinguishes computational complexity from computability theory: the computability theory asks what kind of problems can be solved in principle algorithmically. Computational complexity theory and computability theory are both computer dependent. However, computational complexity theory additionally depends on the storage capacity, the processor speed and the other particulars of the computers that are available at a point in history.
Related to computational theory, a Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine which solves the problem. Because Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory. Many types of Turing machines are used to define complexity classes; these include deterministic Turing machines, probabilistic Turing machines, and non-deterministic Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others. A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used.
The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer (“yes” or “no”). A Turing machine M is said to operate within time f(n), if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) which solves the problem. Because complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria.
A complexity class is a set of problems of related complexity. Simpler complexity classes are defined by the type of computational problem, the model of computation, or the resources that are being bounded and the bounds. Thus, a typical complexity class has a definition like the following: The set of decision problems solvable by a deterministic Turing machine within time f(n).
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.
Because an algorithm may take a different amount of time even on inputs of the same size, the most commonly used measure of time complexity, the worst-case time complexity of an algorithm, denoted as T(n), is the maximum amount of time taken on any input of size n. Time complexities are classified by the nature of the function T(n). For instance, an algorithm with T(n)=O(n), O being a notation for the order of magnitude of the required time, is called a linear time algorithm, and an algorithm with T(n)=O(2n) is said to be an exponential time algorithm.
An algorithm is said to be polynomial time if its running time is upper bounded by a polynomial function of the size of the input for the algorithm, i.e., T(n)=O(nk) for some constant k. The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes that are defined using polynomial time are the P and NP classes. P is the complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time. NP is the complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time.
Thus, the complexity class referred to as P, standing for polynomial, consists of all those decision problems that can be solved on a deterministic sequential machine in an amount of time that is a polynomial of the size of the input. The complexity class NP, standing for non-deterministic polynomial, consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.
The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. Polynomial time is a synonym for “tractable”, “feasible”, “efficient”, or “fast”. All the basic arithmetic operations, addition, subtraction, multiplication, division, and comparison, can be done in polynomial time.
The complexity class NP, on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. Because deterministic Turing machines are a subclass of nondeterministic Turing machines, it is easily observed that each problem in P is also a member of the class NP.
Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at least as difficult as another problem. For instance, if a problem X can be solved using an algorithm for solving problem Y, then problem X is no more difficult than problem Y, and X reduces to Y. There are many different types of reductions based on the method of reduction and the bound on the complexity of reductions.
The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. This can be done by providing the same input to both inputs of the multiplication algorithm. Thus, squaring is not more difficult than multiplication, because squaring can be reduced to multiplication.
A problem X is “hard” for a class of problems C if every problem in C can be reduced to X. Then, no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.
If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C and because there could be many problems which are equally hard, it could be said that X is one of the hardest problems in C. The most difficult problems in NP are called the class of NP-complete problems.